﻿//
// Created by Administrator on 25-9-3.
// 排序算法
//


#ifndef A_SORT_H
#define A_SORT_H
#define NULL nullptr

//最小合并尺寸
#define MIN_MERGE 32
///对外输出快速排序
template<typename E>
extern void quick_sort(E* elements, int left, int right, int (*compare)(const E& e1, const E& e2));
///对外输出tim排序
template<typename E>
extern void tim_sort(E* elements, int size);
extern int calculate_min_run_size(int arr_size);
///tim排序
template<typename E>
void tim_sort(E* elements, int size) {

}

///计算最小run
inline int calculate_min_run_size(int arr_size) {
    int r = 0;
    while (arr_size >= MIN_MERGE) {
        r |= arr_size & 1;
        arr_size >>= 1;
    }
    return arr_size + r;
}



/// 快速排序
template <typename E>
void quick_sort(E* elements, int left, int right, int (*compare)(const E& e1, const E& e2)) {
    if (left >= right) return;
    //选取中间的值为基准值
    const E& pivot = elements[(left + right) / 2];
    int p_left = left;
    int p_right = right;
    while (p_left < p_right) {
        if (compare(elements[p_right], pivot) >= 0) {
            p_right--;
        }
        if (compare(elements[p_left], pivot) <= 0) {
            p_left++;
        }
        const E& tmp = elements[p_right];
        elements[p_right] = elements[p_left];
        elements[p_left] = tmp;
    }
    const E& tmp = elements[p_left];
    elements[p_left] = pivot;
    elements[left] = tmp;
    if (p_left - left > 1) {
        quick_sort(elements, left, p_left);
    }
    if (right - (p_right + 1) > 1) {
        quick_sort(elements, p_right + 1, right);
    }
}

#endif //A_SORT_H
